package com.cheung.leetcode.normal;

import java.util.Arrays;

public class LC33 {

    public static int search(int[] nums, int target) {

        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = (low + high) / 2;
            if (target == nums[mid]) {
                return mid;
            }

            if (nums[mid] > nums[low]) {
                // 说明左边是有序的
                // 判断target在哪边
                if (target < nums[mid] && target >= nums[low]) {
                    // 说明target在左边的有序数组中，接着二分查找
                    high = mid;
                } else {
                    // 说明target在右边的无序数组中
                    low = mid;
                }

            } else {
                // 说明右边有序
                if (target <= nums[high] && target > nums[mid]) {
                    // 说明target在右边的有序数组中，二分查找
                    low = mid;
                } else {
                    // 说明target在左边的无序数组中
                    high = mid;
                }
            }


        }
        return -1;

    }

    public static void main(String[] args) {
        int[] nums = {3, 1};
        System.out.println(Arrays.toString(nums));
        System.out.println(search(nums, 1));
    }
}
